package com.sise.Array;

import java.util.HashSet;
import java.util.Set;

/**
 *      剑指 Offer 03. 数组中重复的数字
 *
 *      找出数组中重复的数字。
 *      在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 *      数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 *
 *      输入：
 *      [2, 3, 1, 0, 2, 5, 3]
 *      输出：2 或 3
 */
public class _offer_03_findRepeatNumber {
    /**
     *  原地置换：使得 num[i] = i，比如 nums[2] = 2
     *  对其进行遍历，第一次遇见数字 x 时，将其交换到索引 x 的位置，当第二次遇见时，一定有 x = nums[x]
     */
    public int findRepeatNumber(int[] nums) {
        if (nums.length == 0) return -1;

        for (int i = 0; i < nums.length; i++){
            while (nums[i] != i){                   // 如果nums[i] == i ，说明此数字已在相应位置
                // 以下相等，说明索引 i 处和索引 nums[i] 处的值都为 nums[i]，如题 [0,1,2,3,2,5,3]，当 i = 4 时，
                // num[4] = 2，nums[nums[4]] = nums[2] = 2，故此相等。
                // 第一个 num[4] 的索引下标为4，第二个 nums[nums[4]] 中的 nums[4] = 2 作为索引下标，如果数值相同，那么说明 2，4 是重复的
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }

                // 如果不相等，那么就交换到到索引下标到位置，比如值为 2 就移动到索引为 2 的位置
                int tmp = nums[i];          // 获取当前位置的数值
                nums[i] = nums[tmp];        // 将目标位置的数值 覆盖 当前位置的数值，要在 tmp 赋值之前完成
                nums[tmp] = tmp;            // 将该数值移动到 自己的索引位置
            }
        }
        return -1;
    }

    /**
     *      利用 hashSet
     */
    public int findRepeatNumber_2(int[] nums) {
            Set<Integer> hashSet = new HashSet<>();
            for (int num : nums){
                if (!hashSet.add(num)) return num;
             }
            return -1;
        }
    }